{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {
    "raw_mimetype": "text/restructuredtext"
   },
   "source": [
    ".. _nb_pso:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ".. meta::\n",
    "   :description: An implementation of the famous Particle Swarm Optimization (PSO) algorithm which is inspired by the behavior of the movement of particles represented by their position and velocity. Each particle is updated considering the cognitive and social behavior in a swarm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ".. meta::\n",
    "   :keywords: Particle Swarm Optimization, Nature-inspired Algorithm, Single-objective Optimization, Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Particle Swarm Optimization (PSO)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Particle Swarm Optimization was proposed in 1995 by Kennedy and Eberhart <cite data-cite=\"pso\"></cite> based on the simulating of social behavior. The algorithm uses a *swarm* of particles to guide its search. Each particle has a velocity and is influenced by locally and globally best-found solutions. Many different implementations have been proposed in the past and, therefore, it is quite difficult to refer to THE correct implementation of PSO. However, the general concepts shall be explained in the following.\n",
    "\n",
    "Given the following variables:\n",
    "\n",
    "- $X_{d}^{(i)}$ d-th coordinate of i-th particle's position\n",
    "- $V_{d}^{(i)}$ d-th coordinate of i-th particle's velocity \n",
    "- $\\omega$ Inertia weight\n",
    "- $P_{d}^{(i)}$ d-th coordinate of i-th particle's *personal* best \n",
    "- $G_{d}^{(i)}$ d-th coordinate of the globally (sometimes also only locally) best solution found\n",
    "- $c_1$ and $c_2$ Two weight values to balance exploiting the particle's best $P_{d}^{(i)}$ and swarm's best $G_{d}^{(i)}$ \n",
    "- $r_1$ and $r_2$ Two random values being create for the velocity update\n",
    "\n",
    "The velocity update is given by:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{equation}\n",
    "V_{d}^{(i)} = \\omega \\, V_{d}^{(i)} \\;+\\; c_1 \\, r_1 \\, \\left(P_{d}^{(i)} - X_{d}^{(i)}\\right) \\;+\\; c_2 \\, r_2 \\, \\left(G_{d}^{(i)} - X_{d}^{(i)}\\right)\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The corresponding position value is then updated by:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{equation}\n",
    "X_{d}^{(i)} = X_{d}^{(i)} + V_{d}^{(i)}\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The social behavior is incorporated by using the *globally* (or locally) best-found solution in the swarm for the velocity update. Besides the social behavior, the swarm's cognitive behavior is determined by the particle's *personal* best solution found.\n",
    "The cognitive and social components need to be well balanced to ensure that the algorithm performs well on a variety of optimization problems.\n",
    "Thus, some effort has been made to determine suitable values for $c_1$ and $c_2$. In **pymoo** both values are updated as proposed in <cite data-cite=\"pso_adapative\"></cite>. Our implementation deviates in some implementation details (e.g. fuzzy state change) but follows the general principles proposed in the paper. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Best solution found: \n",
      "X = [-7.94956179e-09  1.07254590e-07]\n",
      "F = [3.04194228e-07]\n"
     ]
    }
   ],
   "source": [
    "from pymoo.algorithms.so_pso import PSO, PSOAnimation\n",
    "from pymoo.factory import Ackley\n",
    "from pymoo.optimize import minimize\n",
    "\n",
    "problem = Ackley()\n",
    "\n",
    "algorithm = PSO(max_velocity_rate=0.025)\n",
    "\n",
    "res = minimize(problem,\n",
    "               algorithm,\n",
    "               callback=PSOAnimation(fname=\"pso.mp4\"),\n",
    "               seed=1,\n",
    "               save_history=True,\n",
    "               verbose=False)\n",
    "\n",
    "print(\"Best solution found: \\nX = %s\\nF = %s\" % (res.X, res.F))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Assuming you have our third-party library `pyrecorder` installed you can create an animation for a two-dimensional problem easily. Below we provide the code to observe the behavior of the swarm. We have reduced to set the maximum velocity to `max_velocity_rate=0.025` for illustration purposes. Otherwise, the algorithm converges even quicker to the global optimum of the `Ackley` function with two variables."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='text-align:center'>\n",
    "<video width=\"600\" height=\"450\" controls>\n",
    "  <source src=\"http://pymoo.org/animations/pso.mp4\" type=\"video/mp4\">\n",
    "</video>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In general, the PSO algorithm can be used by execute the following code. For the available parameters please see the API description below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "code": "algorithms/usage_pso.py"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Best solution found: \n",
      "X = [-3.07972689e-07  3.05136161e-07]\n",
      "F = [3.72857301e-11]\n"
     ]
    }
   ],
   "source": [
    "from pymoo.algorithms.so_pso import PSO\n",
    "from pymoo.factory import Rastrigin\n",
    "from pymoo.optimize import minimize\n",
    "\n",
    "problem = Rastrigin()\n",
    "\n",
    "algorithm = PSO()\n",
    "\n",
    "res = minimize(problem,\n",
    "               algorithm,\n",
    "               seed=1,\n",
    "               verbose=False)\n",
    "\n",
    "print(\"Best solution found: \\nX = %s\\nF = %s\" % (res.X, res.F))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### API"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "raw_mimetype": "text/restructuredtext"
   },
   "source": [
    ".. autoclass:: pymoo.algorithms.so_pso.PSO\n",
    "    :noindex:\n",
    "    :no-undoc-members:"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Raw Cell Format",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
